﻿#pragma once
//key/value模型
template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode(const std::pair<K, V>& kv=std::pair<K,V>() )
		:_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0)
	{
	}
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf;
	std::pair<K, V> _kv;
};
template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K,V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
				return false;
		}
		cur = new Node(kv);
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		while (parent)
		{
			if (cur == parent->_right)parent->_bf++;
			else parent->_bf--;
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1|| parent->_bf==-1)
			{
				cur = parent;
				parent = cur->_parent;
			}
			else //if (abs(parent->_bf) == 2)
			{
				//旋转处理
				if (parent->_bf == 2)
				{
					//1.左单旋：parent的平衡因子为2（右边高），cur平衡因子为1(右边子树右边高)
					if (cur->_bf == 1)
					{
						RotateL(parent);
					}
					else//3.右左双旋：parent的平衡因子为2（右边高），cur平衡因子为-1(右边子树左边高)
					{
						RotateRL(parent);
					}
				}
				else if (parent->_bf == -2)
				{
					//2.右单旋：parent的平衡因子为-2（左边高），cur平衡因子为-1(左边子树左边高)
					if (cur->_bf == -1)
					{
						RotateR(parent);
					}
					else//3.左右双旋：parent的平衡因子为-2（左边高），cur平衡因子为1(左边子树右边高)
					{
						RotateLR(parent);
					}
				}
				break;//旋转完成后整棵树都不需要再处理，因为旋转区域的高度恢复到插入前的状态
			}
		}
		return true;
	}
	void RotateL(Node* prt)
	{
		//左单旋
		// 涉及的三个位置分别为不平衡根节点prt<subrl<subr：1.subr的subrl给prt右// 2.prt变为subr左
		// 更新每个节点的parent：subrl的parent// prt的parent// subr的parent 
		// 更新平衡因子
		Node* subr = prt->_right;
		Node* subrl = subr->_left;
		//1.处理prt、subr、subr的关系		
		prt->_right = subrl;
		subr->_left = prt;
		//2.处理三者个父节点
		if (subrl)subrl->_parent = prt;//subrl，为空不处理，不为空父节点变为prt
		Node* prt_p = prt->_parent;//处理prt前保留其原有的父节点
		prt->_parent = subr;//prt父节点变为subr
		if (_root == prt)//如果主根就是prt那就要转移主根为subr,并将其父节点置空
		{
			_root = subr;
			subr->_parent = nullptr;
		}
		else//如果prt不直接为主根，判断在prt在原父节点左还是右并将subr移位
		{
			if (prt_p->_left == prt)
				prt_p->_left = subr;
			else
				prt_p->_right = subr;
			subr->_parent = prt_p;
		}
		//3.更新平衡因子
		prt->_bf = subr->_bf = 0;
	}
	void RotateR(Node* prt)
	{
		//右单旋
		// 涉及的三个位置分别为不平衡根节点prt>sublr>subl： 1.subl的sublr给prt左// 2.prt变为subl右
		// 更新每个节点的parent：sublr的parent// prt的parent// subl的parent 
		// 更新平衡因子
		Node* subl = prt->_left;
		Node* sublr = subl->_right;
		//1.处理prt、subl、sublr的关系		
		prt->_left = sublr;
		subl->_right = prt;
		//2.处理三者个父节点
		if (sublr)sublr->_parent = prt;
		Node* prt_p = prt->_parent;
		prt->_parent = subl;
		if (_root == prt)
		{
			_root = subl;
			subl->_parent = nullptr;
		}
		else
		{
			if (prt_p->_left == prt)prt_p->_left = subl;
			else prt_p->_right = subl;
			subl->_parent = prt_p;
		}
		//3.更新平衡因子
		prt->_bf = subl->_bf = 0;
	}
	void RotateRL(Node* ptr)
	{
		Node* subr = ptr->_right;
		Node* subrl = subr->_left;
		int bf = subrl->_bf;//记录优先右旋的左旋节点
		RotateR(ptr->_right);
		RotateL(ptr);
		if (bf == 1)
		{
			ptr->_bf = -1; 
			subr->_bf = 0;
			subrl->_bf = 0;
		}
		else if (bf == -1)
		{		
			subr->_bf = 1;
			ptr->_bf = 0;
			subrl->_bf = 0;
		}
		else if (bf == 0)//实际可以不执行该代码
		{
			subr->_bf = 0;
			ptr->_bf = 0;
			subrl->_bf = 0;
		}
	}
	void RotateLR(Node* ptr)//先左旋后右旋
	{
		Node* subl = ptr->_left;
		Node* sublr = subl->_right;
		int bf = sublr->_bf;//保留先左旋的左节点的右节点平衡因子
		RotateL(ptr->_left);//subl->_bf=0|sublr->_bf=0
		RotateR(ptr);//ptr->_bf=0|subl->_bf=0
		//分析：能进入LR说明0根bf=-2,1左bf=1，整体左高，1左子树右高-》1右为叶子节点bf=0
		//在旋转前如果bf=1，说明插入位置为0根-1左-2右->3右插  2右的（3左必为空）
			//1.先左旋时：2右的左边变为1左  最终得到 2右-（1左（原1左2左|空）|3右插）  
			// 0根-2右-（1左（原1左2左|空）|3右插）
			//2.再右旋时：0根左 左接 2右的右(3右插) 2右做根
			// 2右-（1左（1左原2左|空）|0根（3右插|原0根右）） 
			// 2右：最终会变为该子树根节点左右平衡 所以2右bf正确
			// 1左：左边有原值，右边为空变bf=-1：需要修正
			// 0根：原右子树为叶子节点，左边插入3右插，bf=0；无需修正
		//如果bf=-1：最终3左插会到1左的右边使其左右平衡 无需修正
		// 2右会变为该子树根节点左右平衡无需修正
		// 0根保留其原右边叶子节点，而左边没有新节点，bf=1，需要修正
		//如果bf=0，依然是该旋转操作，但构成该条件的情况2右毕为叶子节点该节点为插入点，
		// 左右旋转后三个bf都为0实际在单旋操作时已被置零无需修正
		if (bf == 1)subl->_bf = -1;
		else if (bf == -1)ptr->_bf = 1;
	}

	void _Inorder(Node* root)
	{
		if (root == nullptr)return;
		_Inorder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_Inorder(root->_right);
	}
	void Inorder()
	{
		_Inorder(_root);
	}
	int _Height(Node* pRoot)
	{
		if (pRoot == nullptr)return 0;
		int lefth = _Height(pRoot->_left);
		int righth = _Height(pRoot->_right);

		return lefth >righth? lefth+1: righth+1;
	}
	bool _IsBalanceTree(Node* pRoot)
	{
		// 空树也是AVL树
		if (nullptr == pRoot) return true;

		// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差
		int leftHeight = _Height(pRoot->_left);
		int rightHeight = _Height(pRoot->_right);
		int diff = rightHeight - leftHeight;
		// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
		// pRoot平衡因子的绝对值超过1，则一定不是AVL树
		if (diff != pRoot->_bf || (diff > 1 || diff < -1))
			return false;
		// pRoot的左和右如果都是AVL树，则该树一定是AVL树
		return _IsBalanceTree(pRoot->_left) && _IsBalanceTree(pRoot->_right);
	}
	bool IsBalanceTree()
	{
		return _IsBalanceTree(_root);
	}
private:
	Node* _root = nullptr;
};

void TestAVLTree1()
{
	cout << "TestAVLTree1" << endl;
	AVLTree<int, int> avlt;
	int arr[] = { 16,3,7,11,9,26,18,14,15 };
	for (auto a : arr)
	{
		avlt.Insert(pair<int, int>(a, a));

	}
	avlt.Inorder();
	cout << avlt.IsBalanceTree() << endl;

	cout << "TestAVLTree1" << endl;
}